package leetcode101.linked_list;

/**
 * @author Synhard
 * @version 1.0
 * @class Code3
 * @description 24. 两两交换链表中的节点
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-06-02 21:29
 */
public class Code3 {

    static class ListNode {
        ListNode next;
        int val;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void main(String[] args) {

    }

    /*
     * @description 递归的方式
     * @param head
     * @return leetcode101.linked_list.Code3.ListNode
     * @author Synhard
     * @date 2021-06-03 15:24
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return head;
    }

    /*
     * @description 迭代的方式
     * @param head
     * @return leetcode101.linked_list.Code3.ListNode
     * @author Synhard
     * @date 2021-06-03 15:25
     */
    public ListNode swapPairs2(ListNode head) {
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        ListNode temp = dummyNode, cur, next;
        while (temp.next != null && temp.next.next != null) {
            cur = temp.next;
            next = cur.next;
            temp.next = next;
            cur.next = next.next;
            next.next = cur;
            temp = cur;
        }
        return dummyNode.next;
    }
}
/*
递归的方式
递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

如果链表中至少有两个节点，则在两两交换链表中的节点之后，
原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。
链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，
更新节点之间的指针关系，即可完成整个链表的两两交换。

迭代的方式
创建头节点dummyHead 令 dummyHead.next = head。令temp表示当前到达的结点，初始时temp = dummyHead
每次交换temp后面的两个结点。如果temp后面没有节点或者只有一个节点则结束，否则获得temp后面的两个结点node1
和node2，通过更新结点指针关系实现两两交换节点。
 */